import java.util.ArrayList;
import java.util.List;

public class Solution216 {
    List<List<Integer>> res;

    public List<List<Integer>> combinationSum3(int k, int n) {
        res = new ArrayList<>();
        if (k * 9 < n) {
            return res;
        }
        dfs(new ArrayList<>(), n, k, 1);
        return res;
    }

    void dfs(List<Integer> list, int target, int k, int start) {
        if (target < 0) {
            return;
        }
        if (k == 0) {
            if (target == 0) {
                res.add(new ArrayList<>(list));
            }
            return;
        }
        for (int i = start; i <= 9; i++) {
            list.add(i);
            dfs(list, target - i, k - 1, i + 1);
            list.remove(list.size() - 1);
        }
    }
}
